package lc20240704;
/**
  * @description 交错字符串
  * @author 不知名帅哥
  * @date 2024/7/4 9:15
  * @version 1.0
*/
public class InterleavedString {
    public boolean isInterleave(String s1, String s2, String s3) {
        int len1 = s1.length();
        int len2 = s2.length();
        int len3 = s3.length();

        // 如果 s1 和 s2 的长度和不等于 s3 的长度，直接返回 false
        if (len1 + len2 != len3) {
            return false;
        }

        // 创建 DP 数组
        boolean[][] dp = new boolean[len1 + 1][len2 + 1];

        // 初始化 DP 数组
        dp[0][0] = true;

        // 填充 DP 数组
        //遍历 dp 数组，根据当前 s1 和 s2 的字符是否等于 s3 的相应位置的字符来更新 dp 数组。
        //如果 s1 的当前字符和 s3 的当前字符相等，并且 dp[i-1][j] 为 true，则 dp[i][j] 为 true。
        //同样地，如果 s2 的当前字符和 s3 的当前字符相等，并且 dp[i][j-1] 为 true，则 dp[i][j] 为 true。
        for (int i = 0; i <= len1; i++) {
            for (int j = 0; j <= len2; j++) {
                if (i > 0) {
                    dp[i][j] = dp[i][j] || (dp[i - 1][j] && s1.charAt(i - 1) == s3.charAt(i + j - 1));
                }
                if (j > 0) {
                    dp[i][j] = dp[i][j] || (dp[i][j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1));
                }
            }
        }

        return dp[len1][len2];
    }

    public static void main(String[] args) {
        String s1="aabcc";
        String s2="dbbca";
        String s3="aadbbbaccc";
        boolean interleave = new InterleavedString().isInterleave(s1, s2, s3);
        System.out.println(interleave);
    }
}
